# -*-coding = utf-8 -*-

# @Time: 2021/4/11 13:24
# @Author: bistro
# @File: p264.py
# @Software: PyCharm
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        m2 = m3 = m5 = 0
        nums = [1]
        while n > 1:
            temp = min(nums[m2] * 2, nums[m3] * 3, nums[m5] * 5)
            if temp == nums[m2] * 2:
                m2 += 1
            if temp == nums[m3] * 3:
                m3 += 1
            if temp == nums[m5] * 5:
                m5 += 1
            nums.append(temp)
            n -= 1
        return nums.pop()


s = Solution()
print(s.nthUglyNumber(1690))